package com.ggqq.day317;

public class Count {
    public static void main(String[] args){
        int[][] grid = {{4,3,2,-1},{3,2,1,-1},{1,1,-1,-2},{-1,-1,-2,-3}};
        Count count = new Count();
        System.out.println(count.countNegatives(grid));

    }

    public int countNegatives(int[][] grid){
        //对二维数组进行第一列列二分查找
        int n = grid.length;//行
        int m = grid[0].length;//列

        int count =0;
        int ind = m;

        for(int i=0;i<n;i++){ //行遍历
//            if(ind==0){//列为0
//                break;
//            }
//            if(grid[i][ind-1]>=0){//列大于0
//                continue;
//            }
            int left = 0,right=ind;

            while(left<right){
                //int mid = (left+right)/2;
                int mid = left+(right-left)/2;
                if(grid[i][mid]>=0){  //相当于行遍历
                    left=mid+1;
                }else {
                    right = mid;
                }
            }
            count += (ind-left)*(n-i);//一行有几个*有多少行
            ind =left;//下一行的rightright指针的初始值可以设置为上一次的结束位置

        }
        return count;
    }
}
